1. Field of the Invention
The present invention relates to a data processing apparatus and method for reducing the size of a lookup table.
2. Description of the Prior Art
Within data processing systems, it is known to employ lookup tables to avoid the need for particular operations to be performed. Instead of the processing circuitry needing to perform a chosen operation, the results of that operation for all possible variants of input are encoded into the lookup table, such that for a particular input data value, that input data value can be provided as an input to the lookup table, with the corresponding output data value representing the result of applying that chosen operation to the input data value then being returned as an output from the lookup table.
The lookup table can be constructed in a variety of ways. Whilst it logically provides a plurality of entries, each entry identifying one possible input data value and the corresponding output data value, the lookup table need not be constructed as a block of memory cells, but instead may be reconstructed using combinations of logic gates used to generate the required output data value for each possible input data value.
However the lookup table is constructed, it can significantly contribute to the overall area and power consumption of the processing circuitry. By way of example, the use of such lookup tables is common within execution units used to implement AES encryption and decryption processes, where the lookup table may be used to provide as output data values the multiplicative inverse of input data values. In particular, such multiplicative inverse values are required as part of the S-box function defined in the AES cryptography Standard.
In that particular example, a 128-bit input value can be split into 16 8-bit sections, and a separate lookup table can then be provided for each 8-bit section. Hence, this results in 16 separate lookup tables, each requiring 256 entries to encode the multiplicative inverse output data values for each of the possible 256 values of the corresponding 8-bit input. It has been found that these lookup tables can occupy the majority of the area of the execution unit used to implement the AES encryption and decryption processes, and that the operation of those lookup tables can contribute very significantly to the overall power consumption.
One known approach for seeking to reduce the size of the lookup tables in the above AES example is to replace the 8-bit Galois field (GF) datapath (a Galois field also being known as a finite field) by two 4-bit GF datapaths or four 2-bit GF datapaths. However, whilst such an approach can save some area in the resultant lookup tables required, the mapping transformations needed to convert the 8-bit GF to and from a 4-bit GF and the 4-bit GF to and from a 2-bit GF are complicated, and may add as much delay to the critical path as they save in a reduced wordlength datapath.
Accordingly, it would be desirable to provide an improved technique for reducing the size of a lookup table implementation, so as to enable a reduction in area and power consumption.